/*
 * @Author: szx
 * @Date: 2021-11-08 15:37:14
 * @LastEditTime: 2021-11-08 16:04:56
 * @Description:
 * @FilePath: \leetcode\1-99\74\74.cpp
 */
#include <iostream>
#include <vector>
using namespace std;
// class Solution {
//    public:
//     bool searchMatrix(vector<vector<int>>& matrix, int target) {
//         int m = matrix.size();
//         int n = matrix[0].size();
//         int all = m * n;
//         int l = 0, r = all;
//         while (l < r) {
//             int mid = (l + r) / 2;
//             cout << mid / m << " " << mid % n << endl;
//             if (matrix[mid / n][mid % n] == target) {
//                 return true;
//             }
//             if (matrix[mid / n][mid % n] > target) {
//                 r = mid;
//             } else {
//                 l = mid + 1;
//             }
//         }
//         return false;
//     }
// };

class Solution {
   public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int l = 0, r = m;
        while (l < r) {
            int mid = (l + r) / 2;
            if (matrix[mid][0] == target) {
                return true;
            }
            if (matrix[mid][0] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int tmp = l - 1;
        l = 0, r = n;
        while (l < r) {
            int mid = (l + r) / 2;
            if (matrix[tmp][mid] == target) {
                return true;
            }
            if (matrix[tmp][mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }
};
int main() {
    cout << 2 % 1 << endl;
    return 0;
}